package problems.daily.y2021m7;

/**
 * @author habitplus
 * @since 2021-07-09 09:04
 */
public class T20210709N1 {
    // 面试题 17.10 主要元素
    // 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
    //
    // 链接：https://leetcode-cn.com/problems/find-majority-element-lcci
    public int majorityElement(int[] nums) {
        // 投票算法：
        // 如果数组中存在主要元素，则一定能得到
        // 如果不存在，则必须进行验证，即判断得到的候选数在数组中出现的次数
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int candidate = nums[0], cnt = 1;

        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                // 当前数位候选数
                candidate = nums[i];
            }
            cnt += (nums[i] == candidate ? 1 : -1);
        }

        // 验证得到的候选数在数组中出现的次数，超过一半即为主要元素
        cnt = 0;
        for (int num : nums) {
            if (candidate == num) {
                cnt++;
            }
        }
        return cnt * 2 - nums.length > 0 ? candidate : -1;
    }

    public static void main(String[] args) {
        System.out.println(new T20210709N1().majorityElement(new int[]{1,2,3,3}));
        System.out.println(new T20210709N1().majorityElement(new int[]{1,2,3,4}));
        System.out.println(new T20210709N1().majorityElement(new int[]{1,2,3}));
        System.out.println(new T20210709N1().majorityElement(new int[]{1,2,2}));
        System.out.println(new T20210709N1().majorityElement(new int[]{1,2,5,9,5,9,5,5,5}));
        System.out.println(new T20210709N1().majorityElement(new int[]{2,2,1,1,1,2,2}));
        System.out.println(new T20210709N1().majorityElement(new int[]{1}));
    }
}
